home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / challenge / 12.01-Jan96 / 12.01ChallengeText.sit / 12.01 Challenge Text next >
Text File  |  1995-12-14  |  5KB  |  102 lines
  1. Sliding Tiles
  2. You have all probably seen small versions of the puzzle that is the basis for
  3. this month’s Challenge:  a 4-by-4 grid of interlocking tiles, with one empty tile
  4. among the 16 cells allowing the puzzle to be scrambled by sliding adjacent cells
  5. into the empty location.   This month the Challenge is to write code that will
  6. unscramble a larger version of the Sliding Tiles puzzle.
  7. The prototype for the code you should write is:
  8.  
  9. typedef Boolean             /*legalMove*/ (*MoveProc)(
  10.                             /* Callback procedure to move tile at        */
  11.   long tileToMoveRow,    /*   these coordinates into the location     */
  12.   long tileToMoveCol     /*   of adjacent empty tile                  */
  13. );
  14.   
  15. void SolveTiles(
  16.   long *tiles,      /* pointer to array of tiles where             */
  17.   long numRows,     /*   tile (row,col) is at                          */
  18.   long numCols,     /*   *(tiles + row*numCols + col)             */
  19.   MoveProc MakeMove /* Callback procedure to move a tile           */
  20. );
  21.  
  22. You will be given a pointer tiles into an array of tile values, the number of
  23. rows and columns in the puzzle (numRows and numCols, respectively), and the
  24. address of a callback procedure MakeMove used to tell my test code about the
  25. moves you make to solve the puzzle.  The tiles array will be initialized with the
  26. values 0..numRows*numCols-1, in an order scrambled by the calling routine.  The
  27. value 0 represents the empty tile.  
  28. Your code should make a sequence of calls to MakeMove and return when the puzzle
  29. is solved.  Each MakeMove call exchanges the empty tile with the indicated
  30. adjacent tile.  The puzzle is solved when you have moved each tile into its
  31. proper location: moving the tile with value i into location tiles[i] (i.e.,
  32. row=i/numCols and col=i%numCols).
  33. The callback routine will be something like the code provided below:
  34.  
  35. static long gNumRows,gNumCols;    /* initialized by test code */
  36. static long gEmptyRow,gEmptyCol;  /* initialized by test code */
  37. static long *gTiles;              /* initialized by test code */
  38.  
  39. #define TileValue(tiles,row,col) *(tiles+(row)*gNumCols+(col))
  40. #define OutOfRange(val,num)  (((val)<0) || ((val)>=(num)))
  41.   
  42. static Boolean MakeMove(long tileToMoveRow,long tileToMoveCol) 
  43. {
  44.   long diff;
  45.   if (OutOfRange(tileToMoveRow,gNumRows)) return false;
  46.   if (OutOfRange(tileToMoveCol,gNumCols)) return false;
  47.   if (tileToMoveRow == gEmptyRow) {
  48.     diff = tileToMoveCol - gEmptyCol;
  49.   } else if (tileToMoveCol == gEmptyCol) {
  50.     diff = tileToMoveRow - gEmptyRow;
  51.   } else {
  52.     return false;
  53.   }
  54.   if ((diff != -1) && (diff != 1)) return false;
  55.   TileValue(gTiles,gEmptyRow,gEmptyCol) = 
  56.     TileValue(gTiles,tileToMoveRow,tileToMoveCol);
  57.   gEmptyRow = tileToMoveRow;
  58.   gEmptyCol = tileToMoveCol;
  59.   TileValue(gTiles,gEmptyRow,gEmptyCol) = 0;
  60. }
  61.  
  62. As an example, given the initial conditions:
  63.  
  64.          long tiles[] = {1,4,0,3,5,2};
  65.          SolveTiles(tiles,2,3,MakeMove);
  66.  
  67. … you could generate the following moves:
  68.  
  69.          MakeMove(1,2);
  70.          MakeMove(1,1);
  71.          MakeMove(0,1);
  72.          MakeMove(0,0);
  73.  
  74. … to transform the puzzle like this:
  75.  
  76.         1 4 0  ==>  1 4 2  ==>  1 4 2  ==>  1 0 2  ==>  0 1 2
  77.         3 5 2       3 5 0       3 0 5       3 4 5       3 4 5
  78.  
  79. It turns out that half of the possible permutations of the values
  80. 0..numRows*numCols-1 are “illegal” in that they cannot be reached from the
  81. “solved” state.  The calling routine will provide a legal starting state – you
  82. don’t have to worry about the puzzle being unsolvable.
  83. The number of moves you make to solve the puzzle is not an explicit criterion in
  84. determining the winner, but the winner will be determined by total execution
  85. time, including the time used by the callback routine, as we did in the Master
  86. MindReader challenge a few months back.  Note that you are not permitted to
  87. optimize the callback routine – its purpose is to provide a fixed time penalty
  88. for each move your solution routine makes.
  89. This will be a native PowerPC Challenge, scored using the Symantec 8.0.3
  90. compiler.  Good luck.  Email me with any questions, or – better yet – join the
  91. Programmer’s Challenge Mailing List …
  92. Mailing List Reminder
  93. Many Challenge readers have already joined the Programmer’s Challenge Mailing
  94. List announced last month.  The list is being used to distribute the latest
  95. Challenge, provide answers to questions about the current Challenge, and discuss
  96. suggestions for future Challenges.  The Challenge problem is posted to the list
  97. sometime between the 20th and the 25th of the month.
  98. To subscribe to the list, send a message to autoshare@mactech.com with the
  99. SUBJECT line “sub challenge YourName”, substituting your real name for YourName. 
  100. To unsubscribe from the list, send a message to autoshare@mactech.com with the
  101. SUBJECT line “unsub challenge”.
  102.